#ifndef ALGO_H_
#define ALGO_H_

#include <cstdint>
#include <type_traits>

namespace lxj
{
// 求两个数的最大公约数
template<class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
inline T gcd(T a, T b)
{
    return b == 0 ? a : gcd(b, a % b);
}

// 求两个数的最小公倍数
template<class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
inline T lcm(T a, T b)
{
    return a / gcd(a, b) * b;
}

// 力扣878. 第 N 个神奇数字
inline int nthMagicalNumber(int n, int a, int b)
{
    int     min = a < b ? a : b;
    int64_t lc  = lcm((int64_t)a, (int64_t)b);
    int64_t ans = 0;
    for (int64_t l = 1, r = (int64_t)n * (int64_t)min, x = 0; l <= r;) {
        x = l + (r - l) / 2;
        if (x / a + x / b - x / lc >= n) {
            ans = x;
            r   = x - 1;
        }
        else {
            l = x + 1;
        }
    }
    return (int)(ans % 1000000007);
}

// 同余原理(+,-,*)
class Congruence {
    int a;
    int b;
    int mod;

public:
    constexpr Congruence(int a, int b, int mod = 1) : a(a), b(b), mod(mod) {}

    inline int add() const
    {
        int ans = a % mod + b % mod;
        return ans % mod;
    }

    inline int sub() const
    {
        const int aa  = a % mod;
        const int bb  = b % mod;
        const int ans = (aa - bb + mod) % mod;
        return ans;
    }

    inline int mul() const
    {
        const int aa  = a % mod;
        const int bb  = b % mod;
        int64_t   ans = (aa * bb) % mod;
        return (int)ans;
    }
};

}   // namespace lxj

#endif